package com.example.sort;

import java.util.Arrays;

/**
 * Created by Quincy on 2018/9/11.
 * 此外在最坏、最佳、平均情况下归并排序时间复杂度均为o(nlogn).从合并过程中可以看出合并排序稳定。
 */
public class MergeSort {

    private MergeSort(){}

    public static void merge(Comparable[] arr, int l, int mid, int r){
        Comparable[] aux = Arrays.copyOfRange(arr, l, r+1);

        int i = l, j = mid + 1;
        for (int k = l; k < r; k++){
            if (i > mid){
                arr[k] = aux[j];
                j++;
            }else if (j > r){
                arr[k] = aux[i];
                i++;
            } else if (aux[i].compareTo(aux[j]) > 0){
                arr[k] = aux[j];
                j++;
            }else {
                arr[k] = aux[i];
                i++;
            }
        }
    }


/**
 * 数组有序情况下，插入排序效果最好，归并排序效果差
 * */
    // 自顶向下
    private static void sort(Comparable[] arr, int l, int r){
        if (l > r) return;
        //小于15，采用插入排序更好
        //TODO
        int mid = (l+r)/2;
        sort(arr, l, mid);
        sort(arr, mid + 1, r);
        //由于归并排序，两边是有序的，如果左边最后一个值小于右边第一个值，则该数组本身就有序的，不需要排序
        if (arr[mid].compareTo(arr[mid + 1]) > 0)  //优化步骤
            merge(arr, l, mid, r);
    }

    private static void sort(Comparable[] arr){
        int l = 0;
        int r = arr.length - 1;
        sort(arr, l, r);
    }

    //自底向上
    public static void mergeBU(Comparable[] arr, int n){
        //sz即是划分的小段
        for (int sz = 0; sz < n; sz+=sz)
            for (int i = 0; i + sz < n; i+= sz + sz)
                //对 arr[i ...i + sz - 1 ] 和 arr[i + sz ... i + 2*sz -1]进行归并
                merge(arr, i, i + sz - 1, Math.min(i + sz + sz - 1 , n - 1));

    }
}
